{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Square Streak in an Array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #binary-search #dynamic-programming #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #二分查找 #动态规划 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestSquareStreak"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数组中最长的方波"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 。如果 <code>nums</code> 的子序列满足下述条件，则认为该子序列是一个 <strong>方波</strong> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>子序列的长度至少为 <code>2</code> ，并且</li>\n",
    "\t<li>将子序列从小到大排序 <strong>之后</strong> ，除第一个元素外，每个元素都是前一个元素的 <strong>平方</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回<em> </em><code>nums</code><em> </em>中 <strong>最长方波</strong> 的长度，如果不存在 <strong>方波</strong><em> </em>则返回<em> </em><code>-1</code> 。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1 ：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [4,3,6,16,8,2]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>选出子序列 [4,16,2] 。排序后，得到 [2,4,16] 。\n",
    "- 4 = 2 * 2.\n",
    "- 16 = 4 * 4.\n",
    "因此，[4,16,2] 是一个方波.\n",
    "可以证明长度为 4 的子序列都不是方波。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2 ：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [2,3,5,6,7]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>nums 不存在方波，所以返回 -1 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>2 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-square-streak-in-an-array](https://leetcode.cn/problems/longest-square-streak-in-an-array/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-square-streak-in-an-array](https://leetcode.cn/problems/longest-square-streak-in-an-array/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,3,6,16,8,2]', '[2,3,5,6,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bisearch(self, lst, idx, tar):\n",
    "        left, right = idx, len(lst)-1\n",
    "        while left < right:\n",
    "            mid = (left+right)//2\n",
    "            if lst[mid] == tar:\n",
    "                return mid\n",
    "            if lst[mid] < tar:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return right\n",
    "\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = {}\n",
    "\n",
    "        idx = 0\n",
    "        for num in nums:\n",
    "            if num**2 > nums[-1]:\n",
    "                break\n",
    "            idx = self.bisearch(nums, idx, num**2)\n",
    "            if num**2 == nums[idx]:\n",
    "                res[num] = nums[idx]\n",
    "        print(res)\n",
    "        \n",
    "        len_dic = {}\n",
    "\n",
    "        def dfs(pa):\n",
    "            if pa not in res:\n",
    "                len_dic[pa] = 1\n",
    "            elif pa not in len_dic.keys():\n",
    "                len_dic[pa] = 1 + dfs(res[pa])\n",
    "            return len_dic[pa]\n",
    "\n",
    "        for key in res.keys():\n",
    "            if key not in len_dic.keys():\n",
    "                dfs(key)\n",
    "        return max(len_dic.values()) if len(len_dic) > 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        dp = [0 for i in range(nums[-1]+1)]\n",
    "        res = -1\n",
    "        for i in nums:\n",
    "            if int(i**(0.5))**2 == i:\n",
    "                dp[i] = dp[int(i**(0.5))] + 1\n",
    "                if dp[i] > 1:\n",
    "                    res = max(res,dp[i])\n",
    "            else:\n",
    "                dp[i] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        stack = [(nums[0], 1)]\n",
    "        res = 1\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] == stack[-1][0]:\n",
    "                continue\n",
    "            while stack and nums[i] > stack[0][0] ** 2:\n",
    "                _, cnt = stack.pop(0)\n",
    "                res = max(res, cnt)\n",
    "            if stack:\n",
    "                tmp = stack[0][0] ** 2\n",
    "            else:\n",
    "                stack.append((nums[i], 1))\n",
    "                continue\n",
    "            if nums[i] == tmp:\n",
    "                n, cnt = stack.pop(0)\n",
    "                stack.append((nums[i], cnt + 1))\n",
    "            elif nums[i] < tmp:\n",
    "                stack.append((nums[i], 1))\n",
    "        \n",
    "        for s in stack:\n",
    "            res = max(res, s[1])\n",
    "        \n",
    "        if res == 1:\n",
    "            return -1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        q = deque()\n",
    "        nums.sort()\n",
    "        last = res = 0\n",
    "        for n in nums:\n",
    "            if n == last: continue\n",
    "            last = n\n",
    "            while q and q[0][0]**2 < n:\n",
    "                q.popleft()\n",
    "            if q and q[0][0]**2 == n:\n",
    "                _, cnt = q.popleft()\n",
    "            else:\n",
    "                cnt = 0\n",
    "            q.append((n, cnt + 1))\n",
    "            res = max(res, cnt + 1)\n",
    "        return res if res > 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        heapify(nums)\n",
    "        s = set(nums)\n",
    "        ans = 0\n",
    "        while s:\n",
    "            tmp = 1\n",
    "            m = heappop(nums)\n",
    "            while m not in s:\n",
    "                m = heappop(nums)\n",
    "            s.remove(m)\n",
    "            while m**2 in s:\n",
    "                m = m**2\n",
    "                s.remove(m)\n",
    "                tmp += 1\n",
    "            ans = max(ans, tmp)\n",
    "        return ans if ans > 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums = sorted(set(nums))\n",
    "        n = len(nums)\n",
    "        ans = [1]*n\n",
    "        idx = 0\n",
    "        res = 0\n",
    "        for i,j in enumerate(nums):\n",
    "            if idx >= n:\n",
    "                break\n",
    "            idx = bisect_right(nums,j*j,idx)\n",
    "            if 0<=idx-1<n and nums[idx-1] == j*j:\n",
    "                ans[idx-1] += ans[i]\n",
    "                res = max(res,ans[idx-1])\n",
    "        return res if res>1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        t = set(nums)\n",
    "        ans = 1\n",
    "        for x in t:\n",
    "            temp = 0\n",
    "            while x in t:\n",
    "                temp += 1\n",
    "                x *= x\n",
    "            ans = max(temp, ans)\n",
    "        return ans if ans > 1 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        ans, s = 0, set(nums)\n",
    "        for x in s:\n",
    "            cnt = 0\n",
    "            while x in s:\n",
    "                cnt += 1\n",
    "                x *= x\n",
    "            ans = max(ans, cnt)\n",
    "        return ans if ans > 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:        \n",
    "        \n",
    "        st = set(nums)\n",
    "        mx = max(nums)\n",
    "        ans = 1  \n",
    "        \n",
    "        for j in range(2,int(mx**.5)+1): # 超过sqrtC的起点没必要枚举了，长度为1都是无效的\n",
    "            p = j\n",
    "            cur = 0\n",
    "            while p in st: # 平方loglogj次就出界了，不会无限循环的\n",
    "                cur+=1\n",
    "                p*=p\n",
    "            ans = max(ans,cur)\n",
    "        return ans if ans>1 else -1 #注意如果找不到长度大于1的，就说明不存在答案，返回-1而不是1\n",
    "    \n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "    nums.sort()\n",
    "    cand = []\n",
    "    q = []\n",
    "    ret = -1\n",
    "    for n in nums:\n",
    "      while len(q) > 0 and n > q[0][0]:      \n",
    "        heapq.heappop(q)\n",
    "\n",
    "      if len(q) > 0 and n == q[0][0]:\n",
    "        c = heapq.heappop(q)\n",
    "        c[1] += 1\n",
    "        c[0] = n * n\n",
    "        ret = max(ret, c[1])\n",
    "        heapq.heappush(q, c)\n",
    "      else:\n",
    "        heapq.heappush(q, [n * n, 1])\n",
    "        \n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        numsset=set(nums)\n",
    "        ans=0\n",
    "        repetition=set()\n",
    "        for i in nums:\n",
    "            if i not in repetition:\n",
    "                repetition.add(i)\n",
    "                jude=True\n",
    "                res=1\n",
    "                j=i\n",
    "                while jude:\n",
    "                    if j**2 in numsset:\n",
    "                        j=j**2\n",
    "                        repetition.add(j)\n",
    "                        res+=1\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                while jude:\n",
    "                    if floor(sqrt(i)+0.5)==sqrt(i) and int(sqrt(i)) in numsset:\n",
    "                       i=int(sqrt(i))\n",
    "                       repetition.add(i)\n",
    "                       res+=1\n",
    "                    else:\n",
    "                        break\n",
    "                ans=max(res,ans)\n",
    "\n",
    "        return ans if ans>1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        m = dict()\n",
    "        ret = 0\n",
    "        nums.sort()\n",
    "        for v in nums:\n",
    "            if not v in m:\n",
    "                m[v] = 1\n",
    "            k = int(sqrt(v))\n",
    "            if k * k == v:\n",
    "                if k in m:\n",
    "                    m[v] = m[k] + 1\n",
    "                    ret = max(ret, m[v])\n",
    "        return ret if ret > 1 else -1\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        f=[1]\n",
    "        dict_=defaultdict(lambda: -1)\n",
    "        max_=1\n",
    "        #print(nums)\n",
    "        dict_[nums[0]]=0\n",
    "        for i in range(1,len(nums)):\n",
    "            f.append(1)\n",
    "\n",
    "            sq=int(sqrt(nums[i]))\n",
    "\n",
    "            if(sq**2==nums[i]):\n",
    "                if(dict_[sq]!=-1):\n",
    "                    f[-1]=1+f[dict_[sq]]\n",
    "                else:\n",
    "                    pass\n",
    "\n",
    "            dict_[nums[i]]=i \n",
    "\n",
    "            max_=max(max_,f[-1])\n",
    "\n",
    "        return -1 if max_==1 else max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        q=set(nums)\n",
    "        nums=sorted(list(q))\n",
    "        visited=set()\n",
    "        ret=0\n",
    "        for i in nums:\n",
    "            visited.add(i)\n",
    "            l=1\n",
    "            temp=i**2\n",
    "            while temp not in visited and temp in q:\n",
    "                visited.add(temp)\n",
    "                temp=temp**2\n",
    "                l+=1\n",
    "            ret=max(ret,l)\n",
    "        if ret>1:\n",
    "            return ret\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums=sorted(nums)\n",
    "        f=[1 for i in range(len(nums))]\n",
    "        dict_=defaultdict(lambda: -1)\n",
    "        max_=1\n",
    "        #print(nums)\n",
    "        dict_[nums[0]]=0\n",
    "        for i in range(1,len(nums)):\n",
    "            #f.append(1)\n",
    "\n",
    "            sq=int(sqrt(nums[i]))\n",
    "\n",
    "            if(sq**2==nums[i]):\n",
    "                if(dict_[sq]!=-1):\n",
    "                    f[i]=1+f[dict_[sq]]\n",
    "                else:\n",
    "                    pass\n",
    "\n",
    "            dict_[nums[i]]=i \n",
    "\n",
    "            max_=max(max_,f[i])\n",
    "\n",
    "        return -1 if max_==1 else max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        while nums:\n",
    "            nums = set(nums) & set([i*i for i in list(nums)])\n",
    "            ans = ans + 1\n",
    "        return ans if ans >= 2 else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [1] * n\n",
    "        nums.sort()\n",
    "        mapper = dict()\n",
    "        i, ans = 0, 0\n",
    "        for i in range(0, n):\n",
    "            t = pow(nums[i], 1 / 2)\n",
    "            if t in mapper:\n",
    "                f[i] = max(f[i], f[mapper[t]] + 1)\n",
    "            mapper[nums[i] * 1.0] = i\n",
    "            ans = max(ans, f[i])\n",
    "        return ans if ans > 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        mx = max(nums)\n",
    "        nums = set(nums)\n",
    "        cnts = {}\n",
    "        for num in nums:\n",
    "            if num in cnts:\n",
    "                continue\n",
    "            cnt = 1\n",
    "            x = num * num\n",
    "            while x <= mx:\n",
    "                if x in cnts:\n",
    "                    cnt += cnts[x]\n",
    "                    break\n",
    "                if x not in nums:\n",
    "                    break\n",
    "                cnt += 1\n",
    "                x *= x\n",
    "            cnts[num] = cnt\n",
    "\n",
    "        mx = max(cnts.values())\n",
    "        return mx if mx > 1 else -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        dict_nums=Counter()\n",
    "        for i in nums:\n",
    "            a=int(sqrt(i))\n",
    "            if a*a!=i:\n",
    "                dict_nums[i]=1\n",
    "                continue\n",
    "            if sqrt(i) not in dict_nums:\n",
    "                dict_nums[i]=1\n",
    "            else:\n",
    "                dict_nums[i]=dict_nums[sqrt(i)]+1\n",
    "        print(dict_nums)\n",
    "        return max(dict_nums.values()) if max(dict_nums.values())!=1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        dict_nums=Counter()\n",
    "        for i in nums:\n",
    "            a=int(sqrt(i))\n",
    "            if a*a!=i:\n",
    "                dict_nums[i]=1\n",
    "                continue\n",
    "            if sqrt(i) not in dict_nums:\n",
    "                dict_nums[i]=1\n",
    "            else:\n",
    "                dict_nums[i]=dict_nums[sqrt(i)]+1\n",
    "        print(dict_nums)\n",
    "        return max(dict_nums.values()) if max(dict_nums.values())!=1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = sorted(nums)\n",
    "        prev = [i for i in range(n)]\n",
    "        \n",
    "        prev_d = {}\n",
    "        \n",
    "        for i, x in enumerate(nums):\n",
    "            if x in prev_d:\n",
    "                prev[i] = prev_d[x]\n",
    "            prev_d[x * x] = i\n",
    "            \n",
    "        count = [1 for i in range(n)]\n",
    "        for i, p in enumerate(prev):\n",
    "            if i == p:\n",
    "                continue\n",
    "            count[i] = 1 + count[p]\n",
    "        z = max(count)\n",
    "        if z >= 2:\n",
    "            return z\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        arr = sorted(list(set(nums)))\n",
    "        cnt = defaultdict(int)\n",
    "        ans = -1\n",
    "        for x in arr:\n",
    "            if cnt[x]:\n",
    "                ans = max(ans, cnt[x] + 1)\n",
    "            cnt[x**2] = cnt[x] + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        num_set = set(nums)\n",
    "        dp = {}\n",
    "        for num in num_set:\n",
    "            dp[num] = 0\n",
    "        def func(x):\n",
    "            if not x in num_set:\n",
    "                return 0\n",
    "            elif dp[x] > 0:\n",
    "                return dp[x]\n",
    "            else:\n",
    "                dp[x] = 1 + func(x * x)\n",
    "                return dp[x]\n",
    "        ans = 0\n",
    "\n",
    "        for num in num_set:\n",
    "            ans = max(ans, func(num))\n",
    "        \n",
    "        if ans < 2:\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import defaultdict, Counter\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "\n",
    "# 给你一个整数数组 nums 。如果 nums 的子序列满足下述条件，则认为该子序列是一个 方波 ：\n",
    "\n",
    "# 子序列的长度至少为 2 ，并且\n",
    "# 将子序列从小到大排序 之后 ，除第一个元素外，每个元素都是前一个元素的 平方 。\n",
    "# 返回 nums 中 最长方波 的长度，如果不存在 方波 则返回 -1 。\n",
    "\n",
    "# 子序列 也是一个数组，可以由另一个数组删除一些或不删除元素且不改变剩余元素的顺序得到。\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        dp = defaultdict(int)\n",
    "        for num in nums[::-1]:\n",
    "            dp[num] = max(dp[num], dp[num**2] + 1)\n",
    "        return max(dp.values()) if max(dp.values()) > 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        f = defaultdict(int)\n",
    "        for num in sorted(nums, reverse=True):\n",
    "            f[num] = f[num * num] + 1\n",
    "            \n",
    "        ans = max(f.values())\n",
    "        return -1 if ans == 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for x in sorted(nums, reverse = True): dic[x] = dic[x*x] + 1    #平方通路,单调\n",
    "        return r if (r := max(dic.values())) > 1 else  -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        dic = defaultdict(int)\n",
    "\n",
    "        l = 1\n",
    "\n",
    "        for n in nums[::-1]:\n",
    "            dic[n] = 1 + dic[n*n]\n",
    "            l = max(l, dic[n])\n",
    "        \n",
    "        if l == 1:\n",
    "            return -1\n",
    "        else:\n",
    "            return l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        ans, s = 0, set(nums)\n",
    "        iii = {num: 0 for num in s}\n",
    "        for num in s:\n",
    "            cnt = iii[num]\n",
    "            while num in s:\n",
    "                cnt += 1\n",
    "                num **= 2\n",
    "            iii[num] = cnt\n",
    "            ans = max(ans, cnt)\n",
    "        return ans if ans > 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        \n",
    "        tmp = Counter(nums)\n",
    "        \n",
    "        def recur(i):\n",
    "            if not tmp[i]:\n",
    "                return 0\n",
    "            tmp[i]-=1\n",
    "            res = recur(i*i)+1\n",
    "            tmp[i]+=1\n",
    "            return res\n",
    "        \n",
    "        res = max(recur(i) for i in set(nums))\n",
    "        if res<2:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        status = dict()\n",
    "        res = 0\n",
    "        def dfs(n):\n",
    "            nonlocal status,l\n",
    "            t = n**2\n",
    "            if t in status:\n",
    "                l += 1\n",
    "                status[t] = 0\n",
    "                dfs(t)  \n",
    "        for i in nums:\n",
    "            status[i] = 1\n",
    "        nums.sort()\n",
    "        for i in nums:\n",
    "            l = 0\n",
    "            if not status[i]:\n",
    "                continue\n",
    "            status[i] = 0\n",
    "            l = 1\n",
    "            dfs(i)\n",
    "            res = max(res,l)\n",
    "        return res if res > 1 else -1\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        def is_square(integer):\n",
    "            root = math.sqrt(integer)\n",
    "            return integer == int(root + 0.5) ** 2\n",
    "        nums.sort()\n",
    "        mapSquare = collections.defaultdict(set)\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            sqrtV = int(num**0.5)\n",
    "            if num not in mapSquare:\n",
    "                    mapSquare[num].add(num)\n",
    "                    if is_square(num) and sqrtV in mapSquare:\n",
    "\n",
    "                        mapSquare[sqrtV].add(num)\n",
    "                        mapSquare[num] = mapSquare[num].union(mapSquare[sqrtV])\n",
    "                        ans = max(len(mapSquare[num]), ans)\n",
    "            #print('num', num, 'sqrtV', sqrtV, mapSquare[num], mapSquare[sqrtV])\n",
    "      \n",
    "        return ans if ans > 0 else -1 \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        val2key = collections.defaultdict(list)\n",
    "        for i in range(len(nums)): \n",
    "            val2key[nums[i]] = i\n",
    "        used = [0] * len(nums)\n",
    "        max_l = 0\n",
    "        for i in range(len(nums)):\n",
    "            if used[i] == 1: continue\n",
    "            \n",
    "            cur_n = nums[i]\n",
    "            cur_l = 1\n",
    "            while val2key[cur_n**2] != []:\n",
    "                idx = val2key[cur_n**2]\n",
    "                used[idx] = 1\n",
    "                cur_n = cur_n**2\n",
    "                cur_l += 1\n",
    "            max_l = max(cur_l, max_l)\n",
    "        return max_l if max_l > 1 else -1\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        # 排序 找平方和\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        s = set(nums)\n",
    "        cur = 1\n",
    "\n",
    "        def dfs(num):\n",
    "            print(num)\n",
    "            nonlocal nums\n",
    "            nonlocal cur\n",
    "            nonlocal s\n",
    "            # 判断当前数平方和是否在数组\n",
    "            if num ** 2 > nums[-1]:\n",
    "                return\n",
    "            if num ** 2 in s:\n",
    "                cur += 1\n",
    "                dfs(num ** 2)\n",
    "\n",
    "        for n in nums:\n",
    "            cur = 1\n",
    "            dfs(n)\n",
    "            ans = max(ans, cur)\n",
    "        return -1 if ans == 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort(reverse=True)\n",
    "        n = len(nums)\n",
    "        mp = defaultdict(int)\n",
    "        for i in range(n):\n",
    "            if mp[nums[i] ** 2] == 0:\n",
    "                mp[nums[i]] = 1\n",
    "            else:\n",
    "                mp[nums[i]] += mp[nums[i] ** 2] + 1\n",
    "        mp = sorted(mp.items(), key = lambda x:x[1], reverse=True)\n",
    "        return mp[0][1] if mp[0][1] >= 2 else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        p = collections.Counter(nums)\n",
    "        q = set()\n",
    "        res = []\n",
    "        nums.sort()\n",
    "\n",
    "        def t(x: int, y: int) -> bool:\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "            if x == y:\n",
    "                return True\n",
    "            while y % x == 0:\n",
    "                y //= x\n",
    "            return y == 0\n",
    "\n",
    "        for i in nums:\n",
    "            if i in q:\n",
    "                continue\n",
    "            q.add(i)\n",
    "            u = set()\n",
    "            u.add(i)\n",
    "            j = i\n",
    "            while j * j in p:\n",
    "                j *= j\n",
    "                u.add(j)\n",
    "                q.add(j)\n",
    "            res.append(u)\n",
    "        ans = 1\n",
    "        for j in res:\n",
    "            ans = max(ans, len(j))\n",
    "        if ans == 1:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        index_map = defaultdict(int)\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        for i,v in enumerate(nums):\n",
    "            index_map[v] = i\n",
    "        \n",
    "        isv = [-1] * len(nums)\n",
    "        res = -1\n",
    "        \n",
    "        max_ = -1\n",
    "        local = 1\n",
    "        def dfs(x):\n",
    "            nonlocal local\n",
    "            nonlocal max_\n",
    "            index = index_map[x]\n",
    "            if isv[index] == 1:\n",
    "                return\n",
    "            isv[index] = 1\n",
    "            local += 1\n",
    "            if x**2 in index_map.keys():\n",
    "                dfs(x**2)\n",
    "            else:\n",
    "                if local > 1:\n",
    "                    max_ = max(max_,local)\n",
    "        for i in range(len(nums)):\n",
    "            if isv[i] == -1:\n",
    "                local = 0\n",
    "                dfs(nums[i])\n",
    "        return max_\n",
    "        \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums = list(set(nums))\n",
    "        nums.sort()\n",
    "        done = set()\n",
    "        d = defaultdict(set)\n",
    "        for e in nums:\n",
    "            done.add(e)\n",
    "            s = sqrt(e)\n",
    "            if int(s)==s:\n",
    "                if s in done:\n",
    "                    while s not in d:\n",
    "                        s = int(sqrt(s))\n",
    "                    d[s].add(e)\n",
    "                else:\n",
    "                    d[e].add(e)\n",
    "            else:\n",
    "                d[e].add(e)\n",
    "        res = -1\n",
    "        for e in d:\n",
    "            if len(d[e])>1:\n",
    "                res = max(res,len(d[e]))\n",
    "        return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(num):\n",
    "            if num*num in nums:\n",
    "                return dfs(num*num)+1\n",
    "            else:\n",
    "                return 1\n",
    "        nums=set(nums)\n",
    "        out=0\n",
    "        for num in nums:\n",
    "            out=max(out,dfs(num))\n",
    "        if out<2:\n",
    "            return -1\n",
    "        return out\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(val):\n",
    "            t = val * val\n",
    "            if t in s:\n",
    "                return dfs(t) + 1\n",
    "            else:\n",
    "                return 1\n",
    "\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            ans = max(ans, dfs(num))\n",
    "        return ans if ans != 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        s=set(nums)\n",
    "        lst=list(s)\n",
    "        lst.sort()\n",
    "        ans=0\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(j):\n",
    "            res=1\n",
    "            if j**2 in s:\n",
    "                return 1+dfs(j**2)\n",
    "            else:\n",
    "                return 1\n",
    "        for i in lst:\n",
    "            ans=max(ans,dfs(i))\n",
    "        if ans>=2:\n",
    "            return ans\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        g=defaultdict(int)\n",
    "        que=sorted(set(nums),reverse=True)\n",
    "        for x in que:\n",
    "            g[x]=-1\n",
    "            if x*x in g:\n",
    "                g[x*x]=x\n",
    "        \n",
    "        @cache\n",
    "        def dfs(cur):\n",
    "            if cur<0:return 0\n",
    "            return 1+dfs(g[cur])\n",
    "        \n",
    "        ans=max(dfs(x) for x in que)\n",
    "        return ans if ans>1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        res, dp, s = -1, {}, set(nums)\n",
    "        def find(i):\n",
    "            if i in dp: return dp[i]\n",
    "            j = i * i\n",
    "            if j in s:\n",
    "                if j not in dp:\n",
    "                    dp[j] = find(j)\n",
    "                dp[i] = dp[j] + 1\n",
    "            else:\n",
    "                dp[i] = 1\n",
    "            return dp[i]\n",
    "        \n",
    "        for i in s:\n",
    "            res = max(res, find(i))\n",
    "        return res if res > 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        nums = set(sorted(nums, reverse=True))\n",
    "        @cache\n",
    "        def search(n):\n",
    "            nxt = n * n\n",
    "            if nxt in nums:\n",
    "                return 1 + search(nxt)\n",
    "            return 1\n",
    "        max_val = 0\n",
    "        for n in nums:\n",
    "            max_val = max(max_val, search(n))\n",
    "        return max_val if max_val != 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        s = set(nums)\n",
    "\n",
    "        @cache\n",
    "        def dfs(x):\n",
    "            if x not in s:\n",
    "                return 0\n",
    "            return 1 + dfs(x * x)\n",
    "\n",
    "        for x in s:\n",
    "            ans = max(ans, 1 + dfs(x * x))\n",
    "        return ans if ans > 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        s = set(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if nums[idx] * nums[idx] in s:\n",
    "                return 1 + dfs(bisect_left(nums, nums[idx] * nums[idx]))\n",
    "            return 1\n",
    "        \n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dfs(i))\n",
    "        dfs.cache_clear()\n",
    "        return ans if ans > 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        len_nums = len(nums)\n",
    "        if len_nums < 2:\n",
    "            return -1\n",
    "        dit = {}\n",
    "        for i in range(len_nums):\n",
    "            dit[nums[i]] = i\n",
    "        dp = [0] * (len_nums + 1)\n",
    "\n",
    "        def dfs(index):\n",
    "            if dp[index] != 0:\n",
    "                return dp[index]\n",
    "            else:\n",
    "                dp[index] = 1\n",
    "            a = nums[index] * nums[index]\n",
    "            if a in dit:\n",
    "                dp[index] = dfs(dit[a]) + 1\n",
    "            return dp[index]\n",
    "\n",
    "        for i in range(len_nums):\n",
    "            dfs(i)\n",
    "        ans = max(dp)\n",
    "        return ans if ans > 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        nums.sort()\n",
    "        s = set(nums)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(idx):\n",
    "            if idx == n:\n",
    "                return 0\n",
    "            \n",
    "            res = 1\n",
    "            num = nums[idx]\n",
    "            n_2 = num * num\n",
    "            if n_2 in s:\n",
    "                i = bisect.bisect_left(nums, n_2)\n",
    "                res += dfs(i)\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        \n",
    "        ans = 1\n",
    "        for i in range(n):\n",
    "            ans = max(ans, dfs(i))\n",
    "        \n",
    "        if ans >= 2:\n",
    "            return ans\n",
    "        return -1\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        ret,s=0,set(nums)\n",
    "        @cache\n",
    "        def dfs(i:int)->int:\n",
    "            if i in s: return dfs(i*i)+1\n",
    "            else: return 0\n",
    "        for i in range(2,10000):\n",
    "            ret=max(ret,dfs(i))\n",
    "        return ret if ret>1 else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        ans, s = 0, set(nums)\n",
    "        @cache\n",
    "        def dfs(x: int) -> int:\n",
    "            if x not in s: return 0\n",
    "            return 1 + dfs(x * x)\n",
    "        for x in s:\n",
    "            ans = max(ans, dfs(x))\n",
    "        return ans if ans > 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        ans, s = 0, set(nums)\n",
    "        @cache\n",
    "        def dfs(x: int) -> int:\n",
    "            if x not in s: return 0\n",
    "            return 1 + dfs(x * x)\n",
    "        for x in s:\n",
    "            ans = max(ans, dfs(x))\n",
    "        return ans if ans > 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSquareStreak(self, nums: List[int]) -> int:\n",
    "        s = set(nums)\n",
    "        @cache\n",
    "        def dfs(x: int) -> int:\n",
    "            if x not in s: return 0\n",
    "            return 1 + dfs(x * x)\n",
    "        ans = max(map(dfs, s))\n",
    "        return ans if ans > 1 else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
